///////////////////////////////////////////////////////////////////////////////////////////////////
/// \file formic/quicksort.h
///
/// \brief   header file for a quicksort function
///
///////////////////////////////////////////////////////////////////////////////////////////////////

#ifndef FORMIC_QUICKSORT_HEADER
#define FORMIC_QUICKSORT_HEADER

#include<formic/random/random.h>

namespace formic {

  ///////////////////////////////////////////////////////////////////////////////////////////////////
  /// \brief   Sorts the range [first,last) into ascending order using the quicksort algorithm.
  ///
  /// \param[in]   first    the beginning of the range
  /// \param[in]   last     the element position immediately following the range to be sorted
  /// \param[in]   work     size >= 4+(last-first).  Workspace for queuing recursive sorts.
  ///                                                If not supplied, it is allocated dynamically.
  ///
  ///////////////////////////////////////////////////////////////////////////////////////////////////
  template <class T> inline void quicksort(T * first, T * last, T ** work = 0) {

    if ( last - first < 2 )
      return;

    bool delete_work = false;
    if ( work == 0 ) {
      work = new T* [4 + (last - first)];
      delete_work = true;
    }

    int task_ind = 2;
    work[0] = first;
    work[1] = last;

    T t;

    while ( task_ind > 0 ) {

      task_ind -= 2;
      T * pvt = work[task_ind+0];
      T * bgn = work[task_ind+0] + 1;
      T * end = work[task_ind+1] - 1;

      // use a randomly chosen pivot
      const int pvt_ind = formic::global_lcg() % (work[task_ind+1]-pvt);
      t = pvt[0];
      pvt[0] = pvt[pvt_ind];
      pvt[pvt_ind] = t;

      while ( bgn != end ) {

        if ( *bgn < *pvt ) {
          bgn++;
        } else {
          t = *bgn;
          *bgn = *end;
          *end = t;
          end--;
        }

      }

      if ( *pvt < *bgn )
        bgn--;
      t = *pvt;
      *pvt = *bgn;
      *bgn = t;

      if ( work[task_ind+1] - bgn > 2 ) {
        work[task_ind+0] = bgn+1;
        //work[task_ind+1] = work[task_ind+1];
        task_ind += 2;
      }
      if ( bgn - pvt > 1 ) {
        work[task_ind+0] = pvt;
        work[task_ind+1] = bgn;
        task_ind += 2;
      }

    }

    if (delete_work)
      delete [] work;

  }

//  ///////////////////////////////////////////////////////////////////////////////////////////////////
//  /// \brief   Sorts the integers in the range [first,last) into ascending order using the quicksort
//  ///          algorithm.
//  ///
//  /// \param[in]   first    the beginning of the range
//  /// \param[in]   last     the element position immediately following the range to be sorted
//  /// \param[in]   work     size >= 4+(last-first).  Workspace for queuing recursive sorts.
//  ///                                                If not supplied, it is allocated dynamically.
//  ///
//  ///////////////////////////////////////////////////////////////////////////////////////////////////
//  inline void quicksort(int * first, int * last, int ** work = 0) {
//
//    if ( last - first < 2 )
//      return;
//
//    bool delete_work = false;
//    if ( work == 0 ) {
//      work = new int* [4 + (last - first)];
//      delete_work = true;
//    }
//
//    int task_ind = 2;
//    work[0] = first;
//    work[1] = last;
//
//    int t;
//
//    while ( task_ind > 0 ) {
//
//      task_ind -= 2;
//      int * pvt = work[task_ind+0];
//      int * bgn = work[task_ind+0] + 1;
//      int * end = work[task_ind+1] - 1;
//
//      // use a randomly chosen pivot
//      const int pvt_ind = formic::global_lcg() % (work[task_ind+1]-pvt);
//      t = pvt[0];
//      pvt[0] = pvt[pvt_ind];
//      pvt[pvt_ind] = t;
//
//      while ( bgn != end ) {
//
//        if ( *bgn < *pvt ) {
//          bgn++;
//        } else {
//          t = *bgn;
//          *bgn = *end;
//          *end = t;
//          end--;
//        }
//
//        //t = *bgn;
//        //const bool bgn_is_lt_pvt_bool = t < *pvt;
//        //const int bgn_is_lt_pvt_int = bgn_is_lt_pvt_bool;
//        //const int bgn_is_ge_pvt_int = !bgn_is_lt_pvt_bool;
//        //*bgn = bgn_is_lt_pvt_int * t      + bgn_is_ge_pvt_int * (*end);
//        //*end = bgn_is_lt_pvt_int * (*end) + bgn_is_ge_pvt_int * t;
//        //bgn += bgn_is_lt_pvt_int;
//        //end -= bgn_is_ge_pvt_int;
//
//      }
//
//      if ( *pvt < *bgn )
//        bgn--;
//      t = *pvt;
//      *pvt = *bgn;
//      *bgn = t;
//
//      if ( work[task_ind+1] - bgn > 2 ) {
//        work[task_ind+0] = bgn+1;
//        //work[task_ind+1] = work[task_ind+1];
//        task_ind += 2;
//      }
//      if ( bgn - pvt > 1 ) {
//        work[task_ind+0] = pvt;
//        work[task_ind+1] = bgn;
//        task_ind += 2;
//      }
//
//    }
//
//    if (delete_work)
//      delete [] work;
//
//  }

}

#endif
